home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / jpegv5asrc.lha / jpeg-5a / wrgif.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-04  |  15.1 KB  |  501 lines
  1. /*
  2.  * wrgif.c
  3.  *
  4.  * Copyright (C) 1991-1994, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains routines to write output images in GIF format.
  9.  *
  10.  * These routines may need modification for non-Unix environments or
  11.  * specialized applications.  As they stand, they assume output to
  12.  * an ordinary stdio stream.
  13.  */
  14.  
  15. /*
  16.  * This code is loosely based on ppmtogif from the PBMPLUS distribution
  17.  * of Feb. 1991.  That file contains the following copyright notice:
  18.  *    Based on GIFENCODE by David Rowley <mgardi@watdscu.waterloo.edu>.
  19.  *    Lempel-Ziv compression based on "compress" by Spencer W. Thomas et al.
  20.  *    Copyright (C) 1989 by Jef Poskanzer.
  21.  *    Permission to use, copy, modify, and distribute this software and its
  22.  *    documentation for any purpose and without fee is hereby granted, provided
  23.  *    that the above copyright notice appear in all copies and that both that
  24.  *    copyright notice and this permission notice appear in supporting
  25.  *    documentation.  This software is provided "as is" without express or
  26.  *    implied warranty.
  27.  *
  28.  * We are also required to state that
  29.  *    "The Graphics Interchange Format(c) is the Copyright property of
  30.  *    CompuServe Incorporated. GIF(sm) is a Service Mark property of
  31.  *    CompuServe Incorporated."
  32.  */
  33.  
  34. #include "cdjpeg.h"        /* Common decls for cjpeg/djpeg applications */
  35.  
  36. #ifdef GIF_SUPPORTED
  37.  
  38.  
  39. #define    MAX_LZW_BITS    12    /* maximum LZW code size (4096 symbols) */
  40.  
  41. typedef INT16 code_int;        /* must hold -1 .. 2**MAX_LZW_BITS */
  42.  
  43. #define LZW_TABLE_SIZE    ((code_int) 1 << MAX_LZW_BITS)
  44.  
  45. #define HSIZE        5003    /* hash table size for 80% occupancy */
  46.  
  47. typedef int hash_int;        /* must hold -2*HSIZE..2*HSIZE */
  48.  
  49. #define MAXCODE(n_bits)    (((code_int) 1 << (n_bits)) - 1)
  50.  
  51.  
  52. /*
  53.  * The LZW hash table consists of two parallel arrays:
  54.  *   hash_code[i]    code of symbol in slot i, or 0 if empty slot
  55.  *   hash_value[i]    symbol's value; undefined if empty slot
  56.  * where slot values (i) range from 0 to HSIZE-1.  The symbol value is
  57.  * its prefix symbol's code concatenated with its suffix character.
  58.  *
  59.  * Algorithm:  use open addressing double hashing (no chaining) on the
  60.  * prefix code / suffix character combination.  We do a variant of Knuth's
  61.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  62.  * secondary probe.
  63.  *
  64.  * The hash_value[] table is allocated from FAR heap space since it would
  65.  * use up rather a lot of the near data space in a PC.
  66.  */
  67.  
  68. typedef INT32 hash_entry;    /* must hold (code_int<<8) | byte */
  69.  
  70. #define HASH_ENTRY(prefix,suffix)  ((((hash_entry) (prefix)) << 8) | (suffix))
  71.  
  72.  
  73. /* Private version of data destination object */
  74.  
  75. typedef struct {
  76.   struct djpeg_dest_struct pub;    /* public fields */
  77.  
  78.   j_decompress_ptr cinfo;    /* back link saves passing separate parm */
  79.  
  80.   /* State for packing variable-width codes into a bitstream */
  81.   int n_bits;            /* current number of bits/code */
  82.   code_int maxcode;        /* maximum code, given n_bits */
  83.   int init_bits;        /* initial n_bits ... restored after clear */
  84.   INT32 cur_accum;        /* holds bits not yet output */
  85.   int cur_bits;            /* # of bits in cur_accum */
  86.  
  87.   /* LZW string construction */
  88.   code_int waiting_code;    /* symbol not yet output; may be extendable */
  89.   boolean first_byte;        /* if TRUE, waiting_code is not valid */
  90.  
  91.   /* State for LZW code assignment */
  92.   code_int ClearCode;        /* clear code (doesn't change) */
  93.   code_int EOFCode;        /* EOF code (ditto) */
  94.   code_int free_code;        /* first not-yet-used symbol code */
  95.  
  96.   /* LZW hash table */
  97.   code_int *hash_code;        /* => hash table of symbol codes */
  98.   hash_entry FAR *hash_value;    /* => hash table of symbol values */
  99.  
  100.   /* GIF data packet construction buffer */
  101.   int bytesinpkt;        /* # of bytes in current packet */
  102.   char packetbuf[256];        /* workspace for accumulating packet */
  103.  
  104. } gif_dest_struct;
  105.  
  106. typedef gif_dest_struct * gif_dest_ptr;
  107.  
  108.  
  109. /*
  110.  * Routines to package compressed data bytes into GIF data blocks.
  111.  * A data block consists of a count byte (1..255) and that many data bytes.
  112.  */
  113.  
  114. LOCAL void
  115. flush_packet (gif_dest_ptr dinfo)
  116. /* flush any accumulated data */
  117. {
  118.   if (dinfo->bytesinpkt > 0) {    /* never write zero-length packet */
  119.     dinfo->packetbuf[0] = (char) dinfo->bytesinpkt++;
  120.     if (JFWRITE(dinfo->pub.output_file, dinfo->packetbuf, dinfo->bytesinpkt)
  121.     != (size_t) dinfo->bytesinpkt)
  122.       ERREXIT(dinfo->cinfo, JERR_FILE_WRITE);
  123.     dinfo->bytesinpkt = 0;
  124.   }
  125. }
  126.  
  127.  
  128. /* Add a character to current packet; flush to disk if necessary */
  129. #define CHAR_OUT(dinfo,c)  \
  130.     { (dinfo)->packetbuf[++(dinfo)->bytesinpkt] = (char) (c);  \
  131.         if ((dinfo)->bytesinpkt >= 255)  \
  132.           flush_packet(dinfo);  \
  133.     }
  134.  
  135.  
  136. /* Routine to convert variable-width codes into a byte stream */
  137.  
  138. LOCAL void
  139. output (gif_dest_ptr dinfo, code_int code)
  140. /* Emit a code of n_bits bits */
  141. /* Uses cur_accum and cur_bits to reblock into 8-bit bytes */
  142. {
  143.   dinfo->cur_accum |= ((INT32) code) << dinfo->cur_bits;
  144.   dinfo->cur_bits += dinfo->n_bits;
  145.  
  146.   while (dinfo->cur_bits >= 8) {
  147.     CHAR_OUT(dinfo, dinfo->cur_accum & 0xFF);
  148.     dinfo->cur_accum >>= 8;
  149.     dinfo->cur_bits -= 8;
  150.   }
  151.  
  152.   /*
  153.    * If the next entry is going to be too big for the code size,
  154.    * then increase it, if possible.  We do this here to ensure
  155.    * that it's done in sync with the decoder's codesize increases.
  156.    */
  157.   if (dinfo->free_code > dinfo->maxcode) {
  158.     dinfo->n_bits++;
  159.     if (dinfo->n_bits == MAX_LZW_BITS)
  160.       dinfo->maxcode = LZW_TABLE_SIZE; /* free_code will never exceed this */
  161.     else
  162.       dinfo->maxcode = MAXCODE(dinfo->n_bits);
  163.   }
  164. }
  165.  
  166.  
  167. /* The LZW algorithm proper */
  168.  
  169.  
  170. LOCAL void
  171. clear_hash (gif_dest_ptr dinfo)
  172. /* Fill the hash table with empty entries */
  173. {
  174.   /* It's sufficient to zero hash_code[] */
  175.   MEMZERO(dinfo->hash_code, HSIZE * SIZEOF(code_int));
  176. }
  177.  
  178.  
  179. LOCAL void
  180. clear_block (gif_dest_ptr dinfo)
  181. /* Reset compressor and issue a Clear code */
  182. {
  183.   clear_hash(dinfo);            /* delete all the symbols */
  184.   dinfo->free_code = dinfo->ClearCode + 2;
  185.   output(dinfo, dinfo->ClearCode);    /* inform decoder */
  186.   dinfo->n_bits = dinfo->init_bits;    /* reset code size */
  187.   dinfo->maxcode = MAXCODE(dinfo->n_bits);
  188. }
  189.  
  190.  
  191. LOCAL void
  192. compress_init (gif_dest_ptr dinfo, int i_bits)
  193. /* Initialize LZW compressor */
  194. {
  195.   /* init all the state variables */
  196.   dinfo->n_bits = dinfo->init_bits = i_bits;
  197.   dinfo->maxcode = MAXCODE(dinfo->n_bits);
  198.   dinfo->ClearCode = ((code_int) 1 << (i_bits - 1));
  199.   dinfo->EOFCode = dinfo->ClearCode + 1;
  200.   dinfo->free_code = dinfo->ClearCode + 2;
  201.   dinfo->first_byte = TRUE;    /* no waiting symbol yet */
  202.   /* init output buffering vars */
  203.   dinfo->bytesinpkt = 0;
  204.   dinfo->cur_accum = 0;
  205.   dinfo->cur_bits = 0;
  206.   /* clear hash table */
  207.   clear_hash(dinfo);
  208.   /* GIF specifies an initial Clear code */
  209.   output(dinfo, dinfo->ClearCode);
  210. }
  211.  
  212.  
  213. LOCAL void
  214. compress_byte (gif_dest_ptr dinfo, int c)
  215. /* Accept and compress one 8-bit byte */
  216. {
  217.   register hash_int i;
  218.   register hash_int disp;
  219.   register hash_entry probe_value;
  220.  
  221.   if (dinfo->first_byte) {    /* need to initialize waiting_code */
  222.     dinfo->waiting_code = c;
  223.     dinfo->first_byte = FALSE;
  224.     return;
  225.   }
  226.  
  227.   /* Probe hash table to see if a symbol exists for
  228.    * waiting_code followed by c.
  229.    * If so, replace waiting_code by that symbol and return.
  230.    */
  231.   i = ((hash_int) c << (MAX_LZW_BITS-8)) + dinfo->waiting_code;
  232.   /* i is less than twice 2**MAX_LZW_BITS, therefore less than twice HSIZE */
  233.   if (i >= HSIZE)
  234.     i -= HSIZE;
  235.  
  236.   probe_value = HASH_ENTRY(dinfo->waiting_code, c);
  237.   
  238.   if (dinfo->hash_code[i] != 0) { /* is first probed slot empty? */
  239.     if (dinfo->hash_value[i] == probe_value) {
  240.       dinfo->waiting_code = dinfo->hash_code[i];
  241.       return;
  242.     }
  243.     if (i == 0)            /* secondary hash (after G. Knott) */
  244.       disp = 1;
  245.     else
  246.       disp = HSIZE - i;
  247.     for (;;) {
  248.       i -= disp;
  249.       if (i < 0)
  250.     i += HSIZE;
  251.       if (dinfo->hash_code[i] == 0)
  252.     break;            /* hit empty slot */
  253.       if (dinfo->hash_value[i] == probe_value) {
  254.     dinfo->waiting_code = dinfo->hash_code[i];
  255.     return;
  256.       }
  257.     }
  258.   }
  259.  
  260.   /* here when hashtable[i] is an empty slot; desired symbol not in table */
  261.   output(dinfo, dinfo->waiting_code);
  262.   if (dinfo->free_code < LZW_TABLE_SIZE) {
  263.     dinfo->hash_code[i] = dinfo->free_code++; /* add symbol to hashtable */
  264.     dinfo->hash_value[i] = probe_value;
  265.   } else
  266.     clear_block(dinfo);
  267.   dinfo->waiting_code = c;
  268. }
  269.  
  270.  
  271. LOCAL void
  272. compress_term (gif_dest_ptr dinfo)
  273. /* Clean up at end */
  274. {
  275.   /* Flush out the buffered code */
  276.   if (! dinfo->first_byte)
  277.     output(dinfo, dinfo->waiting_code);
  278.   /* Send an EOF code */
  279.   output(dinfo, dinfo->EOFCode);
  280.   /* Flush the bit-packing buffer */
  281.   if (dinfo->cur_bits > 0) {
  282.     CHAR_OUT(dinfo, dinfo->cur_accum & 0xFF);
  283.   }
  284.   /* Flush the packet buffer */
  285.   flush_packet(dinfo);
  286. }
  287.  
  288.  
  289. /* GIF header construction */
  290.  
  291.  
  292. LOCAL void
  293. put_word (gif_dest_ptr dinfo, unsigned int w)
  294. /* Emit a 16-bit word, LSB first */
  295. {
  296.   putc(w & 0xFF, dinfo->pub.output_file);
  297.   putc((w >> 8) & 0xFF, dinfo->pub.output_file);
  298. }
  299.  
  300.  
  301. LOCAL void
  302. put_3bytes (gif_dest_ptr dinfo, int val)
  303. /* Emit 3 copies of same byte value --- handy subr for colormap construction */
  304. {
  305.   putc(val, dinfo->pub.output_file);
  306.   putc(val, dinfo->pub.output_file);
  307.   putc(val, dinfo->pub.output_file);
  308. }
  309.  
  310.  
  311. LOCAL void
  312. emit_header (gif_dest_ptr dinfo, int num_colors, JSAMPARRAY colormap)
  313. /* Output the GIF file header, including color map */
  314. /* If colormap==NULL, synthesize a gray-scale colormap */
  315. {
  316.   int BitsPerPixel, ColorMapSize, InitCodeSize, FlagByte;
  317.   int cshift = dinfo->cinfo->data_precision - 8;
  318.   int i;
  319.  
  320.   if (num_colors > 256)
  321.     ERREXIT1(dinfo->cinfo, JERR_TOO_MANY_COLORS, num_colors);
  322.   /* Compute bits/pixel and related values */
  323.   BitsPerPixel = 1;
  324.   while (num_colors > (1 << BitsPerPixel))
  325.     BitsPerPixel++;
  326.   ColorMapSize = 1 << BitsPerPixel;
  327.   if (BitsPerPixel <= 1)
  328.     InitCodeSize = 2;
  329.   else
  330.     InitCodeSize = BitsPerPixel;
  331.   /*
  332.    * Write the GIF header.
  333.    * Note that we generate a plain GIF87 header for maximum compatibility.
  334.    */
  335.   putc('G', dinfo->pub.output_file);
  336.   putc('I', dinfo->pub.output_file);
  337.   putc('F', dinfo->pub.output_file);
  338.   putc('8', dinfo->pub.output_file);
  339.   putc('7', dinfo->pub.output_file);
  340.   putc('a', dinfo->pub.output_file);
  341.   /* Write the Logical Screen Descriptor */
  342.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_width);
  343.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_height);
  344.   FlagByte = 0x80;        /* Yes, there is a global color table */
  345.   FlagByte |= (BitsPerPixel-1) << 4; /* color resolution */
  346.   FlagByte |= (BitsPerPixel-1);    /* size of global color table */
  347.   putc(FlagByte, dinfo->pub.output_file);
  348.   putc(0, dinfo->pub.output_file); /* Background color index */
  349.   putc(0, dinfo->pub.output_file); /* Reserved (aspect ratio in GIF89) */
  350.   /* Write the Global Color Map */
  351.   /* If the color map is more than 8 bits precision, */
  352.   /* we reduce it to 8 bits by shifting */
  353.   for (i=0; i < ColorMapSize; i++) {
  354.     if (i < num_colors) {
  355.       if (colormap != NULL) {
  356.     if (dinfo->cinfo->out_color_space == JCS_RGB) {
  357.       /* Normal case: RGB color map */
  358.       putc(GETJSAMPLE(colormap[0][i]) >> cshift, dinfo->pub.output_file);
  359.       putc(GETJSAMPLE(colormap[1][i]) >> cshift, dinfo->pub.output_file);
  360.       putc(GETJSAMPLE(colormap[2][i]) >> cshift, dinfo->pub.output_file);
  361.     } else {
  362.       /* Grayscale "color map": possible if quantizing grayscale image */
  363.       put_3bytes(dinfo, GETJSAMPLE(colormap[0][i]) >> cshift);
  364.     }
  365.       } else {
  366.     /* Create a gray-scale map of num_colors values, range 0..255 */
  367.     put_3bytes(dinfo, (i * 255 + (num_colors-1)/2) / (num_colors-1));
  368.       }
  369.     } else {
  370.       /* fill out the map to a power of 2 */
  371.       put_3bytes(dinfo, 0);
  372.     }
  373.   }
  374.   /* Write image separator and Image Descriptor */
  375.   putc(',', dinfo->pub.output_file); /* separator */
  376.   put_word(dinfo, 0);        /* left/top offset */
  377.   put_word(dinfo, 0);
  378.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_width); /* image size */
  379.   put_word(dinfo, (unsigned int) dinfo->cinfo->output_height);
  380.   /* flag byte: not interlaced, no local color map */
  381.   putc(0x00, dinfo->pub.output_file);
  382.   /* Write Initial Code Size byte */
  383.   putc(InitCodeSize, dinfo->pub.output_file);
  384.  
  385.   /* Initialize for LZW compression of image data */
  386.   compress_init(dinfo, InitCodeSize+1);
  387. }
  388.  
  389.  
  390. /*
  391.  * Startup: write the file header.
  392.  */
  393.  
  394. METHODDEF void
  395. start_output_gif (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo)
  396. {
  397.   gif_dest_ptr dest = (gif_dest_ptr) dinfo;
  398.  
  399.   if (cinfo->quantize_colors)
  400.     emit_header(dest, cinfo->actual_number_of_colors, cinfo->colormap);
  401.   else
  402.     emit_header(dest, 256, (JSAMPARRAY) NULL);
  403. }
  404.  
  405.  
  406. /*
  407.  * Write some pixel data.
  408.  * In this module rows_supplied will always be 1.
  409.  */
  410.  
  411. METHODDEF void
  412. put_pixel_rows (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo,
  413.         JDIMENSION rows_supplied)
  414. {
  415.   gif_dest_ptr dest = (gif_dest_ptr) dinfo;
  416.   register JSAMPROW ptr;
  417.   register JDIMENSION col;
  418.  
  419.   ptr = dest->pub.buffer[0];
  420.   for (col = cinfo->output_width; col > 0; col--) {
  421.     compress_byte(dest, GETJSAMPLE(*ptr++));
  422.   }
  423. }
  424.  
  425.  
  426. /*
  427.  * Finish up at the end of the file.
  428.  */
  429.  
  430. METHODDEF void
  431. finish_output_gif (j_decompress_ptr cinfo, djpeg_dest_ptr dinfo)
  432. {
  433.   gif_dest_ptr dest = (gif_dest_ptr) dinfo;
  434.  
  435.   /* Flush LZW mechanism */
  436.   compress_term(dest);
  437.   /* Write a zero-length data block to end the series */
  438.   putc(0, dest->pub.output_file);
  439.   /* Write the GIF terminator mark */
  440.   putc(';', dest->pub.output_file);
  441.   /* Make sure we wrote the output file OK */
  442.   fflush(dest->pub.output_file);
  443.   if (ferror(dest->pub.output_file))
  444.     ERREXIT(cinfo, JERR_FILE_WRITE);
  445. }
  446.  
  447.  
  448. /*
  449.  * The module selection routine for GIF format output.
  450.  */
  451.  
  452. GLOBAL djpeg_dest_ptr
  453. jinit_write_gif (j_decompress_ptr cinfo)
  454. {
  455.   gif_dest_ptr dest;
  456.  
  457.   /* Create module interface object, fill in method pointers */
  458.   dest = (gif_dest_ptr)
  459.       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  460.                   SIZEOF(gif_dest_struct));
  461.   dest->cinfo = cinfo;        /* make back link for subroutines */
  462.   dest->pub.start_output = start_output_gif;
  463.   dest->pub.put_pixel_rows = put_pixel_rows;
  464.   dest->pub.finish_output = finish_output_gif;
  465.  
  466.   if (cinfo->out_color_space != JCS_GRAYSCALE &&
  467.       cinfo->out_color_space != JCS_RGB)
  468.     ERREXIT(cinfo, JERR_GIF_COLORSPACE);
  469.  
  470.   /* Force quantization if color or if > 8 bits input */
  471.   if (cinfo->out_color_space != JCS_GRAYSCALE || cinfo->data_precision > 8) {
  472.     /* Force quantization to at most 256 colors */
  473.     cinfo->quantize_colors = TRUE;
  474.     if (cinfo->desired_number_of_colors > 256)
  475.       cinfo->desired_number_of_colors = 256;
  476.   }
  477.  
  478.   /* Calculate output image dimensions so we can allocate space */
  479.   jpeg_calc_output_dimensions(cinfo);
  480.  
  481.   if (cinfo->output_components != 1) /* safety check: just one component? */
  482.     ERREXIT(cinfo, JERR_GIF_BUG);
  483.  
  484.   /* Create decompressor output buffer. */
  485.   dest->pub.buffer = (*cinfo->mem->alloc_sarray)
  486.     ((j_common_ptr) cinfo, JPOOL_IMAGE, cinfo->output_width, (JDIMENSION) 1);
  487.   dest->pub.buffer_height = 1;
  488.  
  489.   /* Allocate space for hash table */
  490.   dest->hash_code = (code_int *)
  491.     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  492.                 HSIZE * SIZEOF(code_int));
  493.   dest->hash_value = (hash_entry FAR *)
  494.     (*cinfo->mem->alloc_large) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  495.                 HSIZE * SIZEOF(hash_entry));
  496.  
  497.   return (djpeg_dest_ptr) dest;
  498. }
  499.  
  500. #endif /* GIF_SUPPORTED */
  501.